字符串的贡献在第一个位置,为了与 对应上考虑将串翻转。
两杯酒 的最大相似度就是 ,即后缀自动机 树上 两个节点的 。
大的相似度会对较小的相似度产生影响,可以看作在后缀树上从深度大的节点考虑。
An Ac a day, keeps the doctor away!
字符串的贡献在第一个位置,为了与 endpos 对应上考虑将串翻转。
两杯酒 p,q 的最大相似度就是 lcp(p,q) ,即后缀自动机 parent 树上 lastp,lastq 两个节点的 lca。
大的相似度会对较小的相似度产生影响,可以看作在后缀树上从深度大的节点考虑。
1⩽i<j⩽n∑len(Ti)+len(Tj)−2×lcp(Ti,Tj)
i=1∑nj=1∑ngcd(i,j)i+j
记 ci 为 i 毫升泡沫的酒在架子上的瓶数,A=maxi=1nai。
为了方便将二元组视为有序,答案除以 2 即可。
i1=1∑ni2=1∑n...if=1∑n[∑ai=n][gcdai=1]